package 排序算法;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 最坏情况下每一个节点需比較log2(n)次。因此其最坏情况下时间复杂度为nlog2(n)。堆排序为不稳定排序，不适合记录较少的排序。
 * @ClassName: HeapSort
 * @Description: TODO(堆排序:)
 * (右子节点-1)/2 获取父节点
 * (父节点*2)+1 左子节点 (父节点*2)+2 右子节点
 * a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
 * 思路:初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。
 * 	然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。
 * 	依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。
 *	 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。
 *          一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数
 * @author xiaok
 * @date 2018年10月3日 下午11:01:12
 *
 */

public class 选择排序_大根堆排序 {
	
	public static void main(String[] args) {

		int[] arr = { 9,6,8,7,0,1,10,4,2 };
		System.out.println(Arrays.toString(arr));
		sort(arr);
		System.out.println(Arrays.toString(arr));
		
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>((a,b) -> a-b);
		queue.offer(2);
		queue.offer(2);
		queue.offer(3);
		queue.offer(5);
		queue.offer(9);
		queue.offer(7);
		queue.offer(1);
		for (Integer i : queue) {
			System.out.print(i+" ");
		}
	}


	public static void sort(int[] a) {
		//最好nlog2n 平均nlog2n 最差nlog2n 空间O1 不稳定
		//建堆
		int start =(a.length-1)/2;
		for(int i=start;i>=0;i--) {
			maxHeap(a, a.length, i);
		}
		//排序
		for (int i = a.length-1; i >0; i--) {
			int temp=a[0];
			a[0]=a[i];
			a[i]=temp;
			maxHeap(a, i, 0);
		}
		
	}
	
	
	//size大根堆的长度,index第一个非叶子节点的父节点,(此方法只是构造大根堆,顺序为大根堆的顺序)
	private static void maxHeap(int[] a,int size,int index) {
		int left =2*index+1;
		int right =2*index+2;
		int max =index;
		if(left<size && a[left]>a[max]) {
			max=left;
		}
		if(right<size && a[right]>a[max]) {
			max=right;
		}
		if(max!=index) {
			int temp=a[index];
			a[index]=a[max];
			a[max]=temp;
			maxHeap(a, size, max);
	}
	}
		
		

}
